The present invention is directed to a forward error correction technique employing the (24, 12) extended Golay code.
A number of decoding methods for the (24, 12) Golay code are known. For hard decision coding, Kasami, T. "A Decoding Procedure for Multiple-Error-Correcting Cyclic Codes," IEEE Transactions on Information Theory, IT-10, pp. 134-139, April, 1964, and Weldon, E. J., "A Comparison of an Interleaved Golay Code and a Three-Dimensional Product Code," Final Report, USNELC, Contract N0095368M 5345, August 1968, proposed two classical techniques which require a large number of logical connections or iterations. (See Lin, S., An Introduction to Error-Correcting Codes, Prentice-Hall, Inc., Englewood Cliffs, NY, 1970). For soft decision decoding, Chase, D., "A Class of Algorithms for Decoding Block Codes with Channel Measurement Information," IEEE Transactions on Information Theory, IT-18, pp. 170-182, 1972, and Weldon, E. J., "Decoding Binary Block Codes on Q-ary Output Channels," IEEE Transactions on Information Theory, IT-17, pp. 713-718, 1971, proposed separate algorithms based on the above-mentioned hard decision algorithms to thereby provide a considerable coding gain.
As solid state technology improves, the list decoding technique for hard decision decoding of block codes becomes more effective compared to the implementation of the classical algebraic algorithms. List decoders with read only memories (RAM) have been implemented for hard decision decoding of BCH codes, as noted in "Final Study Report for IS-838 High-Speed Forward Error Correction Codec," Prepared for INTELSAT, KDD Co, Ltd., Tokyo, Japan, January 1978.
However, the Kasami decoder requires a complicated logic structure, while the Weldon decoder requires a great number of iterations. Further, the Chase method for soft decision decoding requires many trial and error searches. Thus, weighted erasure decoders based on the Kasami decoders are extremely complicated, while the iterative decoding algorithms are generally unsuitable for high-speed operation.